package org.example.Soution002;

import java.util.*;

public class QueenN {
    public static void main(String[] args) {
        QueenN q=new QueenN();
        System.out.println(q.solveNQueens(4));
    }

    /**
     * n皇后要点：不同行，不同列，不同斜
     * 观察斜的特点，可以得到：从左上到右下，同一条斜线上的每个位置满足行下标与列下标之差相等
     *                    从右上到左下，同一条斜线上的每个位置满足行下标与列下标之和相等
     * @param n
     * @return
     */
    List<List<String>> result=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        int[] ans=new int[n];
        Arrays.fill(ans,-1);
        Set<Integer> column=new HashSet<>();
        Set<Integer> bias1=new HashSet<>();//差
        Set<Integer> bias2=new HashSet<>();//和
        core2NQ(ans,n,0,column,bias1,bias2);
        return result;
    }

    public void core2NQ(int[] ans,int n, int row, Set<Integer> column, Set<Integer> bias1, Set<Integer> bias2) {
        if(row==n) {
            result.add(turnToAnswer(ans));
        }
        for(int i=0;i<n;i++){
            if(column.contains(i)) continue;
            int leftUp=row-i;
            if(bias1.contains(leftUp)) continue;
            int rightUp=row+i;
            if(bias2.contains(rightUp)) continue;

            ans[row]=i;
            column.add(i);
            bias1.add(leftUp);
            bias2.add(rightUp);
            core2NQ(ans,n,row+1,column,bias1,bias2);
            ans[row]=-1;
            column.remove(i);
            bias1.remove(leftUp);
            bias2.remove(rightUp);
        }
    }

    public List<String> turnToAnswer(int[] ans) {
        List<String> res=new ArrayList<>();
        for(int i=0;i<ans.length;i++){
            char[] c=new char[ans.length];
            Arrays.fill(c,'.');
            c[ans[i]]='Q';
            res.add(new String(c));
        }
        return res;
    }
}
